package Linked_List.test;

// 一个正确的 MyLinkedList 应该做到什么
// 1) 得是一个合法的线性表
// 2) 当 head != null 则 last != null
// 反之亦然 当 head == null 则 last == null
// 3) 当 head != null 的时候，则 size > 0
// 同理，当 head == null 的时候，则 size == 0
// 4) size 的值应该 == 通过遍历数出来的结点个数 (从 head 到 last 或者 从 last 到 head）
// 5) 除了 head 和 last 之外，所有的其他结点(node), node.prev != null && node.next != null
// 6) head != null 时，则 head.prev == null，但 head.next 不确定（可以不为 null | size > 1）；也可以为 null | size == 1)
//    last != null 时，则 last.next == null，但 last.prev 不确定（可以不为 null | size > 1）；也可以为 null | size == 1)
// 7) 除了 head 和 last 之外的所有结点(node)，node.prev.next == node && node.next.prev == node
// 8) 当 head.next != null 时，head.next.prev == head
//    当 last.prev != null 时，last.prev.next == last
// 9) 当 size == 1 时，head == last && head != null
public class MyLinkedList implements com.peixinchen.java_linked_list.MyList {
    // 维护着 3 个属性
    // 1. 链表的头结点
    private MyNode head;
    // 2. 链表的尾结点
    private MyNode last;
    // 3. 维护着链表中的元素个数
    private int size;   // 不维护也可以通过遍历数出来，但维护好这个属性，可以让 size 的时间复杂度 O(n) -> O(1)

    // 构造方法
    // 构造一个空的链表
    public MyLinkedList() {
        this.head = this.last = null;
        this.size = 0;
    }


    @Override
    public int size() {
        return size;
    }

    // 链表的尾插
    // 时间复杂度：O(1)
    // 和单链表的尾插的区别：已经记录了尾结点，不用遍历找；因为是双向链表，既要处理 next，也要处理 prev
    @Override
    public boolean add(Long e) {
        // 1) 先把元素装到结点中
        MyNode node = new MyNode(e);
        node.next = null;    // 这步可以省略
        // 2) 分情况讨论
        if (size > 0) {
            // 2.1) 链表中有尾结点：last != null 等价于 head != null 等价于 size > 0
            // 3) 找到尾结点 this.last
            this.last.next = node;
            node.prev = this.last;
            this.last = node;
        } else {
            // 2.2) 链表中没有尾结点
            node.prev = null;
            this.head = this.last = node;
        }

        this.size++;

        return true;
    }

    // 链表的头插
    // 时间复杂度：O(1)
    private boolean addFirst(Long e) {
        MyNode node = new MyNode(e);
        node.prev = null;

        if (size > 0) {
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        } else {
            node.next = null;
            this.head = this.last = node;
        }

        this.size++;

        return true;
    }

    public static void main2(String[] args) {
        MyLinkedList list = new MyLinkedList();
        // []
        断言是一个合法的链表(list);

        list.addFirst(100L);
        // [100]
        断言是一个合法的链表(list);
        断言为真(list.size == 1, "size 一定是 1");
        断言链表的某位置一定是(list, 0, 100L);

        list.addFirst(200L);
        // [200, 100]
        断言是一个合法的链表(list);
        断言为真(list.size == 2, "size 一定是 2");
        断言链表的某位置一定是(list, 0, 200L);
        断言链表的某位置一定是(list, 1, 100L);

        System.out.println("测试通过");
    }



    public static void main1(String[] args) {
        MyLinkedList list = new MyLinkedList();
        // []
        断言是一个合法的链表(list);
        list.add(100L);
        // [100]
        断言是一个合法的链表(list);
        断言为真(list.size == 1, "size 一定是 1");
        断言链表的某位置一定是(list, 0, 100L);

        list.add(200L);
        // [100, 200]
        断言是一个合法的链表(list);
        断言为真(list.size == 2, "size 一定是 2");
        断言链表的某位置一定是(list, 0, 100L);
        断言链表的某位置一定是(list, 1, 200L);

        System.out.println("测试通过");
    }

    private static void 断言链表的某位置一定是(MyLinkedList list, int index, long e) {
        // 链表中只能遍历去找，要找 index 的结点，意味着 cur 从 head 开始，向后跳  index 步
        MyNode cur = list.head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        // cur 指向 [index] 下标处的结点
        断言为真(cur.val == e, "该位置的值必须是这个值");
    }

    // 时间复杂度 O(n)
    @Override
    public void add(int index, Long e) {
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }

        if (size == 0) {
//            断言为真(index == 0, "");
            add(e);
//            addFirst(e);
            return;
        }

        if (size == 1) {
            if (index == 0) {
                addFirst(e);
            } else {
                add(e);
            }
            return;
        }

        if (index == 0) {
            addFirst(e);
            return;
        } else if (index == size) {
            add(e);
            return;
        }

        // size  >1 && index > 0 && index < size
        // 链表要插入，是要找到前驱结点
        // 由于我们是双向链表，前驱结点很容易找
        // 先找到前驱结点，记为 prevNode
        MyNode prevNode = this.head;
        for (int i = 0; i < index - 1; i++) {
            prevNode = prevNode.next;   // prevNode 可能会出现 null 么？    不可能
        }

        MyNode curNode = prevNode.next;

        MyNode node = new MyNode(e);
        prevNode.next = node;
        curNode.prev = node;
        node.prev = prevNode;
        node.next = curNode;

        size++;
    }

    public static void main3(String[] args) {
        MyLinkedList list = new MyLinkedList();
        // []

        list.add(0, 100L);  // 测试 size == 0 的情况
        // [ 100L ]
        断言是一个合法的链表(list);
        断言为真(list.size == 1, "size 一定是 1");
        断言链表的某位置一定是(list, 0, 100L);

//        list.add(0, 200L);  // 测试 size == 1 && 头插
//        // [ 200, 100 ]
//        断言是一个合法的链表(list);
//        断言为真(list.size == 2, "size 一定是 2");
//        断言链表的某位置一定是(list, 0, 200L);
//        断言链表的某位置一定是(list, 1, 100L);

        list.add(1, 200L);  // 测试 size == 1 && 尾插
        // [ 100, 200 ]
        断言是一个合法的链表(list);
        断言为真(list.size == 2, "size 一定是 2");
        断言链表的某位置一定是(list, 0, 100L);
        断言链表的某位置一定是(list, 1, 200L);

        list.add(0, 1000L); // 测试 size > 1 && 头插
        // [1000, 100, 200]
        断言是一个合法的链表(list);
        断言为真(list.size == 3, "size 一定是 3");
        断言链表的某位置一定是(list, 0, 1000L);
        断言链表的某位置一定是(list, 1, 100L);
        断言链表的某位置一定是(list, 2, 200L);

        list.add(list.size, 2000L); // 测试 size > 1 && 尾插
        // [1000, 100, 200, 2000]
        断言是一个合法的链表(list);
        断言为真(list.size == 4, "size 一定是 4");
        断言链表的某位置一定是(list, 0, 1000L);
        断言链表的某位置一定是(list, 1, 100L);
        断言链表的某位置一定是(list, 2, 200L);
        断言链表的某位置一定是(list, 3, 2000L);

        list.add(2, 3000L); // 测试 size > && 不是头插 && 不是尾插
        // [1000, 100, 3000, 200, 2000]
        断言是一个合法的链表(list);
        断言为真(list.size == 5, "size 一定是 5");
        断言链表的某位置一定是(list, 0, 1000L);
        断言链表的某位置一定是(list, 1, 100L);
        断言链表的某位置一定是(list, 2, 3000L);
        断言链表的某位置一定是(list, 3, 200L);
        断言链表的某位置一定是(list, 4, 2000L);

        System.out.println("测试成功");
    }

    // 时间复杂度 O(n)
    @Override
    public Long remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }

        if (size == 1) {
            Long e = this.head.val;
            this.head = this.last = null;
            this.size = 0;
            return e;
        }

        // 由于 size 一定是 > 1 的，所以，删除头结点之后，一定是还有结点
        // this.head.next != null 等价于 this.size > 1
        if (index == 0) {
            Long e = this.head.val;

            this.head = this.head.next;
            // 断言 this.head != null
            this.head.prev = null;

            size--;

            return e;
        }

        // this.last.prev != null 等价于 this.size > 1
        if (index == size - 1) {
            Long e = this.last.val;

            this.last = this.last.prev;
            // 断言 this.last != null
            this.last.next = null;

            size--;

            return e;
        }

        // size > 1 && index > 0 && index < size - 1
        MyNode curNode = this.head;
        for (int i = 0; i < index; i++) {
            curNode = curNode.next;     // 断言 curNode != null
        }

        Long e = curNode.val;
        MyNode prevNode = curNode.prev;
        MyNode nextNode = curNode.next;

        // 修改引用关系，删除 curNode
        prevNode.next = nextNode;
        nextNode.prev = prevNode;

        size--;

        return e;
    }

    public static void main4(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.add(100L);
        list.add(200L);
        list.add(300L);
        list.add(400L);
        list.add(500L);
        // [100, 200, 300, 400, 500]

        // size > 1 && 中间位置删除
        Long e = list.remove(2);
        // [100, 200, 400, 500]
        断言是一个合法的链表(list);
        断言为真(list.size == 4, "size 一定是 4");
        断言链表的某位置一定是(list, 0, 100L);
        断言链表的某位置一定是(list, 1, 200L);
        断言链表的某位置一定是(list, 2, 400L);
        断言链表的某位置一定是(list, 3, 500L);
        断言为真(e == 300L, "元素一定是 300");

        // size > 1 && 头删
        e = list.remove(0);
        // [200, 400, 500]
        断言是一个合法的链表(list);
        断言为真(list.size == 3, "size 一定是 3");
        断言链表的某位置一定是(list, 0, 200L);
        断言链表的某位置一定是(list, 1, 400L);
        断言链表的某位置一定是(list, 2, 500L);
        断言为真(e == 100L, "元素一定是 100");

        // size > 1 && 尾删
        e = list.remove(2);
        // [200, 400]
        断言是一个合法的链表(list);
        断言为真(list.size == 2, "size 一定是 2");
        断言链表的某位置一定是(list, 0, 200L);
        断言链表的某位置一定是(list, 1, 400L);
        断言为真(e == 500L, "元素一定是 500");

        // size > 1 && 尾删
        e = list.remove(1);
        // [200]

        // size == 1
        e = list.remove(0);
        // []
        断言是一个合法的链表(list);
        断言为真(list.size == 0, "size 一定是 0");
        断言为真(e == 200L, "元素一定是 200");

        System.out.println("测试成功");
    }

    // 删除从前向后查找过程中第一次遇到的 e
    @Override
    public boolean remove(Long e) {
        MyNode cur = this.head;
        for (int i = 0; i < size; i++) {
            // size >= 1
            if (cur.val.equals(e)) {
                // 就是我们要删除的元素
                // index == 0; index == size - 1; 剩下的情况
                if (i == 0) {
                    // 此时 size 的可能性 >= 1
                    this.head = this.head.next;
                    // 此刻无法断言 this.head != null
                    // size == 1 则 此时 this.head == null
                    // size > 1 则 此时 this.head != null
                    if (this.head != null) {
                        this.head.prev = null;
                    } else {
                        // 此刻 this.head == null
                        this.last = null;
                    }

                    size--;
                    return true;
                }

                if (i == size - 1) {
                    // size > 1
                    this.last = this.last.prev;
                    this.last.next = null;
                    // 这里加上 else { this.head = null; } 一定没错，但可以不加

                    size--;
                    return true;
                }

                // 既不是头删，也不是尾删
                MyNode prevNode = cur.prev;
                MyNode nextNode = cur.next;
                // cur 既不是头也不是尾，并且在一个线性表中
                // 说明 cur 一定有前驱 && 一定有后继
                // 此刻 断言 prevNode != null && nextNode != null
                prevNode.next = nextNode;
                nextNode.prev = prevNode;

                size--;
                return true;
            }

            cur = cur.next;
        }

        return false;
    }

    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.add(100L);
        list.add(100L);
        list.add(100L);
        list.add(100L);
        list.add(200L);
        // [100, 100, 100, 100, 200]

        boolean r = list.remove(100L);
        断言是一个合法的链表(list);
        断言为真(list.size == 4, "size 一定是 4");
        断言链表的某位置一定是(list, 0, 100L);
        断言链表的某位置一定是(list, 1, 100L);
        断言链表的某位置一定是(list, 2, 100L);
        断言链表的某位置一定是(list, 3, 200L);
        断言为真(r, "删除一定成功");

        r = list.remove(1000L);
        断言是一个合法的链表(list);
        断言为真(list.size == 4, "size 一定是 4");
        断言链表的某位置一定是(list, 0, 100L);
        断言链表的某位置一定是(list, 1, 100L);
        断言链表的某位置一定是(list, 2, 100L);
        断言链表的某位置一定是(list, 3, 200L);
        断言为真(r == false, "删除一定失败");

        // [100, 100, 100, 200]
        r = list.remove(200L);
        断言是一个合法的链表(list);
        断言为真(list.size == 3, "size 一定是 3");
        断言链表的某位置一定是(list, 0, 100L);
        断言链表的某位置一定是(list, 1, 100L);
        断言链表的某位置一定是(list, 2, 100L);
        断言为真(r, "删除一定成功");

        // [100, 100, 100]
        r = list.remove(100L);
        断言是一个合法的链表(list);
        断言为真(list.size == 2, "size 一定是 2");
        断言链表的某位置一定是(list, 0, 100L);
        断言链表的某位置一定是(list, 1, 100L);
        断言为真(r, "删除一定成功");
        // [100, 100]
        r = list.remove(100L);
        断言是一个合法的链表(list);
        断言为真(list.size == 1, "size 一定是 1");
        断言链表的某位置一定是(list, 0, 100L);
        断言为真(r, "删除一定成功");
        // [100]
        r = list.remove(100L);
        断言是一个合法的链表(list);
        断言为真(list.size == 0, "size 一定是 0");
        断言为真(r, "删除一定成功");
        // []
        r = list.remove(100L);
        断言是一个合法的链表(list);
        断言为真(list.size == 0, "size 一定是 0");
        断言为真(r == false, "删除一定失败");

        list = new MyLinkedList();
        list.add(100L);
        list.add(200L);
        list.add(300L);
        list.add(400L);
        // [100, 200, 300, 400]
        r = list.remove(300L);
        // [100, 200, 400]
        断言是一个合法的链表(list);
        断言为真(list.size == 3, "size 一定是 3");
        断言链表的某位置一定是(list, 0, 100L);
        断言链表的某位置一定是(list, 1, 200L);
        断言链表的某位置一定是(list, 2, 400L);
        断言为真(r, "删除一定成功");

        System.out.println("测试成功");
    }

    // O(n)
    @Override
    public Long get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }

        MyNode cur = this.head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        return cur.val;
    }

    // O(n)
    @Override
    public Long set(int index, Long e) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }

        MyNode cur = this.head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        Long oldValue = cur.val;
        cur.val = e;
        return oldValue;
    }

    @Override
    public int indexOf(Long e) {
        int i = 0;
        MyNode cur = this.head;
        while (cur != null) {
            if (cur.val.equals(e)) {
                return i;
            }

            i++;
            cur = cur.next;
        }

        return -1;
    }

    @Override
    public int lastIndexOf(Long e) {
        int i = size - 1;
        MyNode cur = this.last;
        while (cur != null) {
            if (cur.val.equals(e)) {
                return i;
            }
            i--;
            cur = cur.prev;
        }

        return -1;
    }

    @Override
    public boolean contains(Long e) {
        return indexOf(e) != -1;
    }

    @Override
    public void clear() {
        this.head = this.last = null;
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private static void 断言为真(boolean condition, String message) {
        if (!condition) {
            throw new RuntimeException(message);
        }
    }

    private static void 检查2(MyLinkedList list) {
        if (list.head == null) {
            断言为真(list.last == null, "head 为 null 时，last 必须是 null");
        } else {
            断言为真(list.last != null, "head 不为 null 时，last 必须不为 null");
        }
    }

    private static void 检查3(MyLinkedList list) {
        断言为真(list.size >= 0, "size 必须 >= 0");

        if (list.head == null) {
            断言为真(list.size == 0, "head 为 null 时，size 必须是 0");
        } else {
            断言为真(list.size > 0, "head 不为 null 时，size 必须大于 0");
        }
    }

    private static int 从前往后遍历确定结点个数(MyLinkedList list) {
        int size = 0;
        for (MyNode cur = list.head; cur != null; cur = cur.next) {
            size++;
        }

        return size;
    }

    private static void 检查4(MyLinkedList list) {
        断言为真(list.size == 从前往后遍历确定结点个数(list), "记录的 size 应该和遍历出的 size 相等");
    }

    private static void 检查5(MyLinkedList list) {
        if (list.size > 1) {
            MyNode cur = list.head.next;
            while (cur != list.last) {
                断言为真(cur.prev != null, "非头尾结点的 prev 不能是 null");
                断言为真(cur.next != null, "非头尾结点的 next 不能是 null");

                cur = cur.next;
            }
        }
    }

    private static void 检查6(MyLinkedList list) {
        // head != null 等价于 size > 0
        if (list.head != null) {
            断言为真(list.head.prev == null, "头结点的 prev 一定是 null");
            断言为真(list.last.next == null, "尾结点的 next 一定是 null");
            if (list.size == 1) {
                断言为真(list.head.next == null, "size 为 1 时，头节点的 next 一定是 null");
                断言为真(list.last.prev == null, "size 为 1 时，为节点的 prev 一定是 null");
            } else {
                断言为真(list.head.next != null, "size > 1 时，头节点的 next 一定不是 null");
                断言为真(list.last.prev != null, "size > 1 时，尾节点的 prev 一定不是 null");
            }

        }
    }

    private static void 检查7(MyLinkedList list) {
        if (list.size > 1) {
            MyNode cur = list.head.next;    // 跳过头节点
            while (cur != list.last) {      // 跳过尾结点
                断言为真(cur.prev.next == cur, "非头尾结点的 前驱的 后继是自己");
                断言为真(cur.next.prev == cur, "非头尾结点的 后继的 前驱是自己");

                cur = cur.next;
            }
        }
    }

    private static void 检查8(MyLinkedList list) {
        // head.next != null 等价于 last.prev != null 等价于 size > 1
        if (list.size > 1) {
            断言为真(list.head.next.prev == list.head, "当 head.next != null 时，head.next.prev == head");
            断言为真(list.last.prev.next == list.last, "当 last.prev != null 时，last.prev.next == last");
        }
    }

    private static void 断言是一个合法的链表(MyLinkedList list) {
        检查2(list);
        检查3(list);
        检查4(list);
        检查5(list);
        检查6(list);
        检查7(list);
        检查8(list);
    }
}
